An FPGA is a programmable logic device that has an array of configurable logic blocks (CLBs) connected together via a programmable routing structure. A typical FPGA may have tens of thousands of CLBs, each CLB having a plurality of primitive logic cells. Primitive cells of a CLB may include, e.g., flip-flops interconnected in a variety of ways to implement a desired logic function corresponding to that CLB. For example, each CLB may have lookup tables, multiplexers, and/or registers.
FIGS. 1A–B illustrate a representative FPGA architecture. In particular, FIG. 1A shows schematically an FPGA 100 comprising a plurality of CLBs 102 surrounded by input-output (I/O) blocks 104 and interconnected through a routing structure 106. CLBs 102 are typically connected to form a plurality of nets, one of which, net 110, is depicted in FIG. 1B. Illustratively, net 110 has ten CLBs 102 interconnected via routing structure 106 (not shown in FIG. 1B) as indicated by the solid lines. The physical dimensions of net 110 are characterized by a bounding box 120 of height a and width b shown by the dashed lines in FIG. 1B. A different net may include a different number of CLBs 102 and/or one or more I/O blocks 104. Each CLB 102 and/or I/O block 104 may belong to more than one net.
When an FPGA, such as FPGA 100 of FIG. 1, comprises thousands of CLBs in a large number of nets, the task of establishing the required multitude of interconnections between the CLBs in a net and between the different nets becomes so onerous that it requires CAD implementation. Accordingly, manufacturers of FPGAs including the assignee hereof, Lattice Semiconductor, Inc., develop place-and-route CAD tools to be used, e.g., by their customers (FPGA programmers) to implement their respective circuit designs. Typically, place-and-route software implements an iterative process aimed at producing a circuit configuration that meets certain customer specifications, such as insertion delays between specified pins and/or operation (clock) frequency. A relatively large number of iterations may be needed to reach an acceptable configuration because, for example, of the unknown impact of CLB placement on routing resources, such as wires of structure 106. As a result, finding an optimum configuration may require substantial computer resources. For a similar reason, only a sub-optimal configuration might be found within the allotted (or feasible) computer time, the implementation of which configuration will not exercise the full potential of the hardware and will unnecessarily limit the circuit performance.